package zuo.algo.c07;

import zuo.algo.data.TreeNode;
import zuo.algo.util.TreeUtils;

/**
 * 00:37-判断一个树是否是平衡二叉树
 * 左树是平衡二叉树，右树是平衡二叉树，且左树和右树高度差不大于1
 */
public class IsBST {

    public static boolean isBST(TreeNode head) {
        return bst(head).bst;
    }

    public static Info bst(TreeNode head) {
        if (head == null) {
            return new Info(true, 0);
        }
        Info leftInfo = bst(head.left);
        Info rightInfo = bst(head.right);
        boolean isBst = leftInfo.bst && rightInfo.bst
                && Math.abs(leftInfo.high - rightInfo.high) <= 1;
        int high = Math.max(leftInfo.high, rightInfo.high) + 1;
        return new Info(isBst, high);
    }

    public static class Info {
        public boolean bst;
        public int high;

        public Info(boolean bst, int high) {
            this.bst = bst;
            this.high = high;
        }
    }

    public static void main(String[] args) {
        TreeNode head = TreeUtils.getTree();
        boolean bst = isBST(head);
        System.out.println(bst);
        head.right.right.right.right = new TreeNode(22);
        bst = isBST(head);
        System.out.println(bst);
    }
}
